<!DOCTYPE html>
<html lang="en">
<head><meta name="generator" content="Hexo 3.8.0">
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="威龙的博客">
    <meta name="keyword" content="随缘">
    <link rel="shortcut icon" href="/img/favicon.ico">

    <title>
        
        堆排序 - 威龙的博客 | VeyronC&#39;s Blog
        
    </title>

    <!-- Custom CSS -->
    <link rel="stylesheet" href="/css/aircloud.css">
    <link rel="stylesheet" href="/css/gitment.css">
    <!--<link rel="stylesheet" href="https://imsun.github.io/gitment/style/default.css">-->
    <link href="//at.alicdn.com/t/font_620856_pl6z7sid89qkt9.css" rel="stylesheet" type="text/css">
    <!-- ga & ba script hoook -->
    <script></script>
</head>

<body>

<div class="site-nav-toggle" id="site-nav-toggle">
    <button>
        <span class="btn-bar"></span>
        <span class="btn-bar"></span>
        <span class="btn-bar"></span>
    </button>
</div>

<div class="index-about">
    <i> 心若水， 自非凡。该博客已迁移至 https://www.cnblogs.com/xrszff </i>
</div>

<div class="index-container">
    
    <div class="index-left">
        
<div class="nav" id="nav">
    <div class="avatar-name">
        <div class="avatar">
            <img src="/img/avatar.jpg">
        </div>
        <div class="name">
            <i>威龙</i>
        </div>
    </div>
    <div class="contents" id="nav-content">
        <ul>
            <li>
                <a href="/">
                    <i class="iconfont icon-shouye1"></i>
                    <span>主页</span>
                </a>
            </li>
            <li>
                <a href="/tags">
                    <i class="iconfont icon-biaoqian1"></i>
                    <span>标签</span>
                </a>
            </li>
            <li>
                <a href="/archive">
                    <i class="iconfont icon-guidang2"></i>
                    <span>存档</span>
                </a>
            </li>
            <li>
                <a href="/about/">
                    <i class="iconfont icon-guanyu2"></i>
                    <span>关于</span>
                </a>
            </li>
            
            <li>
                <a id="search">
                    <i class="iconfont icon-sousuo1"></i>
                    <span>搜索</span>
                </a>
            </li>
            
        </ul>
    </div>
    
        <div id="toc" class="toc-article">
    <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#大根堆"><span class="toc-text">大根堆</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#小根堆"><span class="toc-text">小根堆</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#找到数组中最小的k个数"><span class="toc-text">找到数组中最小的k个数</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#找数组中最大的k个数或是第k大的数"><span class="toc-text">找数组中最大的k个数或是第k大的数</span></a></li></ol>
</div>
    
</div>


<div class="search-field" id="search-field">
    <div class="search-container">
        <div class="search-input">
            <span id="esc-search"> <i class="icon-fanhui iconfont"></i></span>
            <input id="search-input">
            <span id="begin-search">搜索</span>
        </div>
        <div style="padding:10px 20px;font=10;">
            若搜索无反应请更换浏览器~
        </div>
        <div class="search-result-container" id="search-result-container">

        </div>
    </div>
</div>
        <div class="index-about-mobile">
            <i> 心若水， 自非凡。该博客已迁移至 https://www.cnblogs.com/xrszff </i>
        </div>
    </div>
    
    <div class="index-middle">
        <!-- Main Content -->
        


<div class="post-container">
    <div class="post-title">
        堆排序
    </div>

    <div class="post-meta">
        <span class="attr">发布于：<span>2017-07-12 19:57:56</span></span>
        
        <span class="attr">标签：/
        
        <a class="tag" href="/tags/#排序" title="排序">排序</a>
        <span>/</span>
        
        
        </span>
        <span class="attr">访问：<span id="busuanzi_value_page_pv"></span>
</span>

    </div>
    <div class="post-content no-indent">
        <p><strong>堆排序其实就是操作数组，交换数组元素</strong></p>
<ol>
<li>假设数组长度为 n，则从数组的 (n/2 - 1) 这个元素开始向下调整建立堆。</li>
<li>调整函数中，左右孩子下标分别是，<code>2 * i + 1</code>和<code>2 * i + 2</code>。</li>
<li>建堆和排序都用到了调整函数。</li>
</ol>
<ul>
<li>大根堆用来从小到大排序，找到数组中最小的k个数</li>
<li>小根堆用来从大到小排序，找到数组中最大的k个数</li>
</ul>
<h1 id="大根堆"><a href="#大根堆" class="headerlink" title="大根堆"></a>大根堆</h1><figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">class HeapSort &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="keyword">int</span>* heapSort(<span class="keyword">int</span>* A, <span class="keyword">int</span> n) &#123;</span><br><span class="line">        buildHeap(A, n);  <span class="comment">// 建立大根堆</span></span><br><span class="line">        <span class="built_in">for</span> (<span class="keyword">int</span> i = n - <span class="number">1</span>; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">            swap(A[<span class="number">0</span>], A[i]);</span><br><span class="line">            adjustHeap(A, <span class="number">0</span>, i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">return</span> A;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">void</span> buildHeap(<span class="keyword">int</span>* A, <span class="keyword">int</span> n) &#123;</span><br><span class="line">        <span class="built_in">for</span> (<span class="keyword">int</span> i = n / <span class="number">2</span> - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--)  <span class="comment">// 这个初始位置 n / 2 - 1 记住</span></span><br><span class="line">            adjustHeap(A, i, n);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">void</span> adjustHeap(<span class="keyword">int</span>* A, <span class="keyword">int</span> i, <span class="keyword">int</span> n) &#123;  <span class="comment">// 从 i 这个位置一直调整到 n 位置</span></span><br><span class="line">        <span class="keyword">int</span> lChild = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> rChild = <span class="number">2</span> * i + <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span> <span class="built_in">max</span> = i;</span><br><span class="line">        <span class="built_in">if</span> ((lChild &lt; n) &amp;&amp; A[lChild] &gt; A[<span class="built_in">max</span>])</span><br><span class="line">            <span class="built_in">max</span> = lChild;</span><br><span class="line">        <span class="built_in">if</span> ((rChild &lt; n) &amp;&amp; A[rChild] &gt; A[<span class="built_in">max</span>])</span><br><span class="line">            <span class="built_in">max</span> = rChild;</span><br><span class="line">        <span class="built_in">if</span> (<span class="built_in">max</span> != i)&#123;</span><br><span class="line">            swap(A[<span class="built_in">max</span>], A[i]);</span><br><span class="line">            adjustHeap(A, <span class="built_in">max</span>, n);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h1 id="小根堆"><a href="#小根堆" class="headerlink" title="小根堆"></a>小根堆</h1><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="comment">// 这里是小根堆的写法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">adjustHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> i, <span class="keyword">int</span> n)</span> </span>&#123;  <span class="comment">// 从 i 这个位置一直调整到 n 位置</span></span><br><span class="line">    <span class="keyword">int</span> lChild = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> rChild = <span class="number">2</span> * i + <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span> min = i;</span><br><span class="line">    <span class="keyword">if</span> ((lChild &lt; n) &amp;&amp; A[lChild] &lt; A[min])  <span class="comment">// if ((lChild &lt; n) &amp;&amp; A[lChild] &gt; A[max])</span></span><br><span class="line">        min = lChild;  <span class="comment">// max = lChild;</span></span><br><span class="line">    <span class="keyword">if</span> ((rChild &lt; n) &amp;&amp; A[rChild] &lt; A[min])  <span class="comment">// if ((rChild &lt; n) &amp;&amp; A[rChild] &gt; A[max])</span></span><br><span class="line">        min = rChild; <span class="comment">// max = rChild;</span></span><br><span class="line">    <span class="keyword">if</span> (min != i) &#123;  <span class="comment">//if (max != i)&#123;</span></span><br><span class="line">        swap(A[min], A[i]);  <span class="comment">// swap(A[max], A[i]);</span></span><br><span class="line">        adjustHeap(A, min, n);  <span class="comment">// adjustHeap(A, max, n);</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">buildHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n / <span class="number">2</span> - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--)  <span class="comment">// 这个初始位置 n / 2 - 1 记住</span></span><br><span class="line">        adjustHeap(A, i, n);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">heapSort</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    buildHeap(A, n);  <span class="comment">// 建堆</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n - <span class="number">1</span>; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">        swap(A[<span class="number">0</span>], A[i]);</span><br><span class="line">        adjustHeap(A, <span class="number">0</span>, i);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> a[] = &#123;<span class="number">3</span>,<span class="number">4</span>,<span class="number">8</span>,<span class="number">100</span>,<span class="number">2</span>,<span class="number">-3</span>,<span class="number">23</span>,<span class="number">11</span>,<span class="number">44</span>,<span class="number">61</span>&#125;;</span><br><span class="line">    <span class="keyword">int</span> n = <span class="keyword">sizeof</span>(a) / <span class="keyword">sizeof</span>(<span class="keyword">int</span>);</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; input(a, a+n);</span><br><span class="line">    </span><br><span class="line">    heapSort(input, n);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; input.size(); i++)</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; input[i] &lt;&lt; <span class="string">"  "</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="找到数组中最小的k个数"><a href="#找到数组中最小的k个数" class="headerlink" title="找到数组中最小的k个数"></a>找到数组中最小的k个数</h1><ol>
<li>首先从数组中取出k个数，建一个大小为k的大根堆</li>
<li>然后依次拿剩余数据和大根堆的堆顶比较，若当前剩余数据比堆顶大，那么这个数不可能是最小的k个数之一。如果比对堆顶小，交换它们，并调整大根堆。</li>
<li>重复2过程，直到原数组遍历完。</li>
</ol>
<p>在上面大根堆代码基础上，main()函数不同，其他函数相同:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="comment">// 这里是大根堆的写法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">adjustHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> i, <span class="keyword">int</span> n)</span> </span>&#123;  <span class="comment">// 从 i 这个位置一直调整到 n 位置</span></span><br><span class="line">    <span class="keyword">int</span> lChild = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> rChild = <span class="number">2</span> * i + <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span> max = i;</span><br><span class="line">    <span class="keyword">if</span> ((lChild &lt; n) &amp;&amp; A[lChild] &gt; A[max])</span><br><span class="line">        max = lChild;</span><br><span class="line">    <span class="keyword">if</span> ((rChild &lt; n) &amp;&amp; A[rChild] &gt; A[max])</span><br><span class="line">        max = rChild;</span><br><span class="line">    <span class="keyword">if</span> (max != i)&#123;</span><br><span class="line">        swap(A[max], A[i]);</span><br><span class="line">        adjustHeap(A, max, n);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">buildHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n / <span class="number">2</span> - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--)  <span class="comment">// 这个初始位置 n / 2 - 1 记住</span></span><br><span class="line">        adjustHeap(A, i, n);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; findMinK(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> k)&#123;</span><br><span class="line">    <span class="comment">// 若要取数组中最小的k个树，先取出最前面k个数，建立大根堆</span></span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; minK(A.begin(), A.begin() + k);</span><br><span class="line">    buildHeap(minK, k);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = k; i &lt; A.size(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (A[i] &lt; minK[<span class="number">0</span>])&#123;</span><br><span class="line">            minK[<span class="number">0</span>] = A[i];</span><br><span class="line">            adjustHeap(minK, <span class="number">0</span>, k);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> minK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> a[] = &#123;<span class="number">3</span>,<span class="number">4</span>,<span class="number">8</span>,<span class="number">100</span>,<span class="number">2</span>,<span class="number">-3</span>,<span class="number">23</span>,<span class="number">11</span>,<span class="number">44</span>,<span class="number">61</span>&#125;;</span><br><span class="line">    <span class="keyword">int</span> n = <span class="keyword">sizeof</span>(a) / <span class="keyword">sizeof</span>(<span class="keyword">int</span>);</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; input(&amp;a[<span class="number">0</span>], &amp;a[n]);</span><br><span class="line">    </span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; minK = findMinK(input,<span class="number">4</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; minK.size(); i++)</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; minK[i] &lt;&lt; <span class="string">"  "</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h1 id="找数组中最大的k个数或是第k大的数"><a href="#找数组中最大的k个数或是第k大的数" class="headerlink" title="找数组中最大的k个数或是第k大的数"></a>找数组中最大的k个数或是第k大的数</h1><p>编程二：找出数组中的第k大的数，但是题目测试用例输入奇葩，说是两行：</p>
<ul>
<li>第一行是正式数列，数字用空格分隔，如：45 67 33 21</li>
<li>第二行是一个整数k，代表数组长度范围内的第K大的K，如：2</li>
</ul>
<p>这例子输出：45</p>
<p>这里输入的处理是，全部用while，cin进向量里面，然后最后一个元素取出来当做k，前面所有元素当做数组。<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="comment">// 这里是小根堆的写法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">adjustHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> i, <span class="keyword">int</span> n)</span> </span>&#123;  <span class="comment">// 从 i 这个位置一直调整到 n 位置</span></span><br><span class="line">    <span class="keyword">int</span> lChild = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> rChild = <span class="number">2</span> * i + <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span> min = i;</span><br><span class="line">    <span class="keyword">if</span> ((lChild &lt; n) &amp;&amp; A[lChild] &lt; A[min])</span><br><span class="line">        min = lChild; </span><br><span class="line">    <span class="keyword">if</span> ((rChild &lt; n) &amp;&amp; A[rChild] &lt; A[min])</span><br><span class="line">        min = rChild; </span><br><span class="line">    <span class="keyword">if</span> (min != i) &#123; </span><br><span class="line">        swap(A[min], A[i]);</span><br><span class="line">        adjustHeap(A, min, n);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">buildHeap</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = n / <span class="number">2</span> - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--)  <span class="comment">// 这个初始位置 n / 2 - 1 记住</span></span><br><span class="line">        adjustHeap(A, i, n);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; findMaxK(<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;&amp; A, <span class="keyword">int</span> k)&#123;</span><br><span class="line">    <span class="comment">// 若要取数组中最大的k个树，先取出最前面k个数，建立小根堆</span></span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; maxK(A.begin(), A.begin() + k);</span><br><span class="line">    buildHeap(maxK, k);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = k; i &lt; A.size(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (A[i] &gt; maxK[<span class="number">0</span>])&#123;</span><br><span class="line">            maxK[<span class="number">0</span>] = A[i];</span><br><span class="line">            adjustHeap(maxK, <span class="number">0</span>, k);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> maxK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> tmp;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; input;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; tmp) &#123;</span><br><span class="line">        input.push_back(tmp);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> k = input[input.size() - <span class="number">1</span>];</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; rec(input.begin(), input.end() - <span class="number">1</span>);</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; maxK = findMaxK(input,k);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; maxK[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

        
            <div class="donate-container">
    <div class="donate-button">
        <button id="donate-button">赞赏</button>
    </div>
    <div class="donate-img-container hide" id="donate-img-container">
        <img id="donate-img" src data-src="/img/donate.jpg">
        <p> 感谢鼓励 </p>
    </div>
</div>
        
        <br>
        <div id="comment-container">
        </div>
        <div id="disqus_thread"></div>

        <div id="lv-container">
        </div>

    </div>
</div>

    </div>
</div>


<footer class="footer">
    <ul class="list-inline text-center">
        
        

        
        <li>
            <a target="_blank" href="http://weibo.com/2983694150">
                            <span class="fa-stack fa-lg">
                                  <i class="iconfont icon-weibo"></i>
                            </span>
            </a>
        </li>
        

        

        

        

    </ul>
    
    <p>
        <span>/</span>
        
        <span><a href="https://www.10000h.top">10000H</a></span>
        <span>/</span>
        
        <span><a href="https://niexiaotao.com">Xiaotao&#39;s Page</a></span>
        <span>/</span>
        
        <span><a href="#">It helps SEO</a></span>
        <span>/</span>
        
    </p>
    
    <p>
        <span id="busuanzi_container_site_pv">
            <span id="busuanzi_value_site_pv"></span>PV
        </span>
        <span id="busuanzi_container_site_uv">
            <span id="busuanzi_value_site_uv"></span>UV
        </span>
        Created By <a href="https://hexo.io/">Hexo</a>  Theme <a href="https://github.com/aircloud/hexo-theme-aircloud">AirCloud</a></p>
</footer>




</body>

<script>
    // We expose some of the variables needed by the front end
    window.hexo_search_path = "search.json"
    window.hexo_root = "/"
    window.isPost = true
</script>
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.min.js"></script>
<script src="/js/index.js"></script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>


    <script>
        /**
         *  RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
         *  LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables
        */
        if( '' || '')
        var disqus_config = function () {
            this.page.url = '';  // Replace PAGE_URL with your page's canonical URL variable
            this.page.identifier = ''; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
        };

        (function() { // DON'T EDIT BELOW THIS LINE
            var d = document, s = d.createElement('script');
            s.src = 'https://airclouds-blog.disqus.com/embed.js';
            s.setAttribute('data-timestamp', +new Date());
            (d.head || d.body).appendChild(s);
        })();
    </script>



</html>
